package myTree;

public class BuildBTree {
    public static MyBTree createBTPreIn(String pre, String in) {//由先序序列pre和中序序列in构造二叉链
        MyBTree bt = new MyBTree();
        bt.b = createBTPreIn1(pre, 0, in, 0, pre.length());
        return bt;
    }

    private static BTNode<Character> createBTPreIn1(String pre, int i, String in, int j, int n) {
        BTNode<Character> t;
        char ch;
        int p, k;
        if (n <= 0) return null;
        ch = pre.charAt(i);
        //创建根结点(结点值为ch)
        t = new BTNode<Character>(ch);
        //p指中序序列的开始元素
        p = j;
        //在in中找等于ch的位置p
        while (p < j + n) {
            if (in.charAt(p) == ch) break;
            p++;
        }
        //确定左子树中结点个数k
        k = p - j;
        //递归构造左子树
        t.lchild = createBTPreIn1(pre, i + 1, in, j, k);
        //递归构造右子树
        t.rchild = createBTPreIn1(pre, i + k + 1, in, p + 1, n - k - 1);
        return t;
    }

    public static MyBTree createBTPostIn(String post, String in)
    //由后序序列post和中序序列in构造二叉链
    {
        MyBTree bt = new MyBTree();
        bt.b = createBTPostIn1(post, 0, in, 0, post.length());
        return bt;
    }

    private static BTNode<Character> createBTPostIn1(String post, int i, String in, int j, int n) {
        BTNode<Character> t;
        char ch;
        int p, k;
        if (n <= 0) return null;
        ch = post.charAt(i + n - 1);        //取后序序列尾元素
        t = new BTNode<Character>(ch);    //创建根结点(结点值为ch)
        p = j;                    //p指中序序列的开始元素
        while (p < j + n)            //在中序序列中找根位置p
        {
            if (in.charAt(p) == ch) break;            //在in中找到根后退出
            p++;
        }
        //确定左子树中结点个数k
        k = p - j;
        //递归构造左子树
        t.lchild = createBTPostIn1(post, i, in, j, k);
        //递归构造右子树
        t.rchild = createBTPostIn1(post, i + k, in, p + 1, n - k - 1);
        return t;
    }


}

